package com.yulan.BitOpt;

import org.junit.Test;

import java.util.ArrayList;

/**
 * 生成第k个素数
 */
public class TheKPrimeNumber {
    private boolean[] prime = new boolean[10000000];

    //获取k之前的所有素数
    private void initAllPrimeNumBeforeK(int k){
        prime[0] = false;
        prime[1] = true;
        for(int i = 2; i <= k; i++){
            if(prime[i]) continue;
            for(int j = i*i; j<=k; j+= i){
                prime[j] = true;
            }
        }
    }

    private ArrayList<Integer> getAllPrimeNumBeforeK(int k){
        initAllPrimeNumBeforeK(k);
        ArrayList<Integer> ans = new ArrayList<>();
        for(int i=2; i<k; i++){
            if(!prime[i]) ans.add(i);
        }
        return ans;
    }

    private boolean isPrime(int a){
        if(a == 1) return false;
        if(a == 2 || a == 3) return true;
        if(a % 6 != 1 && a % 6 != 5) return false;
        int tmp = (int) Math.sqrt(a);
        for(int i=5; i<=tmp; i+=6){

            if(a % i == 0 || a % (i + 2) == 0) return false;
        }
        return true;
    }

    private ArrayList<Integer> getAllPrimeNumBeforeK2(int k){
        ArrayList<Integer> ans = new ArrayList<>();
        for(int i=1; i<=k; i++){
            if(isPrime(i)) ans.add(i);
        }
        return ans;
    }



    @Test
    public void test(){
//        getAllPrimeNumBeforeK(100).forEach(System.out::println);
        ArrayList<Integer> ans = getAllPrimeNumBeforeK2(10000);
        System.out.println(ans.size());
    }
}
